Coding decimal numbers with factorials is a way of writing out numbers in a base system >that depends on factorials, rather than powers of numbers.
In this system, the last digit is always 0 and is in base 0!. The digit before that is >either 0 or 1 and is in base 1!. The digit before that is either 0, 1, or 2 and is in >base 2!, etc. More generally, the nth-to-last digit is always 0, 1, 2, ..., n and is in >base n!.
Read more about it at: http://en.wikipedia.org/wiki/Factorial_number_system
Example
The decimal number 463 is encoded as "341010", because
463 = 3×5! + 4×4! + 1×3! + 0×2! + 1×1! + 0×0!If we are limited to digits 0..9, the biggest number we can encode is 10!-1 (= >3628799). So we extend 0..9 with letters A..Z. With these 36 digits we can now encode >numbers up to 36!-1 (= 3.72 × 1041)
Task
We will need two functions. The first one will receive a decimal number and return a >string with the factorial representation.The second one will receive a string with a factorial representation and produce the >decimal representation.
Given numbers will always be positive.
題目理解:設計兩個函式,能將數字以階乘數系統的形式作轉換。
故463轉換後會得到"341010",如下:
463 = 3×5! + 4×4! + 1×3! + 0×2! + 1×1! + 0×0!
另題目要求將A~Z也代入擴展,意即最大可表達的數為37!-1。 (10個數字加上26字母故最高可表達位數是36!)
故:371993326789901217467999448150835199999999 = "ZYXWVUTSRQPONMLKJIHGFEDCBA9876543210"
可利用math.factorial()輔助解題如下:
import math
#將所有階乘位數的字元,依序建立成字串供後續輸出時調用
all_digit = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
def biggest_digit(num):
"找出一個數字轉換為階乘數系統後,將其最大的階乘位數&係數以(d ,m)形式返還"
#依序檢驗 d! 與 num的關係
for d in range(1,37):
#若 d!大於num,代表其最大位數為(d-1)!
if math.factorial(d)>num:
#再依序檢驗其係數m乘上(d-1)!後與num的關係即可得知m,須留意m的最大範圍為d本身(詳見階乘數系統關於基數之說明)
for m in range(1,d+1):
if math.factorial(d-1)*m >num:
return (d-1,m-1)
elif math.factorial(d-1)*m == num:
return (d-1,m)
#若d!洽等於num則代表:num = d! * 1 ,故直接返還(d , 1)
elif math.factorial(d) == num:
return (d,1)
def dec_2_fact_string(nb):
"""將數字nb以階乘數系統方式表達"""
lst = []
dic = {}
number = nb
reslut = ""
#不斷找number其最大階乘位數&係數,找到後就將number減去 digtl! * multiplier,直到number不足0
while number > 0:
digit,multiplier= biggest_digit(number)
#將(digtl,multiplier)存入lst備用
lst.append((digit,multiplier))
number -= math.factorial(digit)*multiplier
#將lst中的每個元組,以digit為key,multiplier為值存入
for digit,multiplier in lst:
dic[digit] = all_digit[multiplier]
#lst中的第一個元組的digtl會是整個nb的最大位數,故從最大位數開始往下檢查看每個位數是否有出現在dic.keys()中
for i in range(lst[0][0],0,-1):
#若有則代表有對應的multiplier
if i in dic.keys():
reslut += str(dic[i])
#若無代表該位數上multiplier為0
else: reslut+="0"
#最後結果須再補上最小位數 0!*0
return reslut+"0"
def fact_string_2_dec(string):
"""將以階乘數系統表達的字串轉換成十進位數字"""
reslut = 0
for m in range(1,len(string)+1):
digit_ind = string[-m]
#digit_ind在all_digit中的索引值即為其代表的階乘位數
reslut += math.factorial(m-1)*int(all_digit.index(digit_ind))
return reslut